package leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-16 16:47
 **/
public class LeetCode382 {
    ListNode head;
    Random random;
    //水塘抽样
    public LeetCode382(ListNode head) {
        random = new Random();
        this.head = head;
    }

    public int getRandom() {
        int i = 1;
        ListNode temp = head;
        int res = 0;
        while (temp != null) {
            if (random.nextInt(i) == 0) {
                res = temp.val;
            }
            ++i;
            temp = temp.next;
        }

        return res;
    }

    //存储链表元素
    /*List<Integer> list;
    Random random;

    public LeetCode382(ListNode head) {
        list = new ArrayList<>();
        random = new Random();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
    }

    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }*/

}
